import java.util.Arrays;

class Solution673 {
    public static void main(String[] args) {
       int[] arr = { 1,2,4,3,5,4,7,2} ;
        System.out.println(findNumberOfLIS(arr));
    }
    public static int findNumberOfLIS(int[] nums) {
        int  n = nums.length ;
        //状态表示:
        // len[i] 以i 结尾的最长子序列  长度
        int[] len = new int[n] ;
        // count[i] 以 i 结尾的最长子序列 个数
        int[] count = new int[n] ;

        // 记录 最长子序列长度
        int max = Integer.MIN_VALUE ;
        // 记录最长子序列 出现个数
        int maxCount = 0 ;
        for(int i=0 ; i <n ; i ++){
            // 初始化:
            // len[] 和 count[] 所有的值初始化为 : 1 以最差情况来记录
            len[i] = count[i] = 1 ;
            for(int j=i-1 ; j >= 0 ; j --){
                // 第 i 个 可以跟 到 第 j 个的后面的
                if(nums[i] > nums[j]){
                    if(len[j]+1 > len[i]){   //有长度 比当前的大的, 更新最大长度,和 最大长度个数
                       len[i] = len[j] + 1 ;
                       count[i] = count[j] ;
                    }else if(len[j]+1 == len[i]){// 第j个跟上i 的长度 等于 最大长度的
                        // 更新 最大长度个数
                        count[i] += count[j] ;
                    }
                }
            }
            // 更新 最大长度 和 最大长度出现个数
            if(max < len[i]){
                // 如果max了 , 更新 最大长度和 出现个数
                max = len[i] ;
                maxCount = count[i] ;
            }else if(max == len[i]){
                // 如果相同 则出现个数加上 当前以 i 结尾的最长子序列的 个数
                maxCount += count[i] ;
            }

        }
        return maxCount ;
    }
}
